{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Increasing Triplet Subsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: increasingTriplet"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #递增的三元子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组&nbsp;<code>nums</code> ，判断这个数组中是否存在长度为 <code>3</code> 的递增子序列。</p>\n",
    "\n",
    "<p>如果存在这样的三元组下标 <code>(i, j, k)</code>&nbsp;且满足 <code>i &lt; j &lt; k</code> ，使得&nbsp;<code>nums[i] &lt; nums[j] &lt; nums[k]</code> ，返回 <code>true</code> ；否则，返回 <code>false</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3,4,5]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>任何 i &lt; j &lt; k 的三元组都满足题意\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [5,4,3,2,1]\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>不存在满足题意的三元组</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [2,1,5,0,4,6]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>三元组 (3, 4, 5) 满足题意，因为 nums[3] == 0 &lt; nums[4] == 4 &lt; nums[5] == 6\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 5 * 10<sup>5</sup></code></li>\n",
    "\t<li><code>-2<sup>31</sup> &lt;= nums[i] &lt;= 2<sup>31</sup> - 1</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong>你能实现时间复杂度为 <code>O(n)</code> ，空间复杂度为 <code>O(1)</code> 的解决方案吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [increasing-triplet-subsequence](https://leetcode.cn/problems/increasing-triplet-subsequence/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [increasing-triplet-subsequence](https://leetcode.cn/problems/increasing-triplet-subsequence/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5]', '[5,4,3,2,1]', '[2,1,5,0,4,6]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        N = len(nums)\n",
    "        first_smallest = inf-1\n",
    "        second_smallest = inf\n",
    "        for i in range(N):\n",
    "            if nums[i]<=first_smallest:\n",
    "                first_smallest = nums[i]\n",
    "            elif nums[i]<=second_smallest:\n",
    "                second_smallest = nums[i]\n",
    "            else:\n",
    "                return True\n",
    "        return False\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        first = float('inf')\n",
    "        second = float('inf')\n",
    "        for num in nums:\n",
    "            if num <= first:\n",
    "                first = num\n",
    "            elif num <= second:\n",
    "                second = num\n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        res=[float('inf'),float('inf')]\n",
    "        for i in nums:\n",
    "            if i>res[1]:\n",
    "                return True\n",
    "            elif i<=res[0]:\n",
    "                res[0]=i\n",
    "            else:\n",
    "                res[1]=i\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        nums_low_1, nums_low_2 = float('inf'), float('inf')\n",
    "        for num in nums:\n",
    "            if nums_low_1>=num:\n",
    "                nums_low_1 = num\n",
    "            elif nums_low_2>=num:\n",
    "                nums_low_2 = num\n",
    "            else:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: 'List[int]') -> 'bool':\n",
    "        if len(nums) < 3: return False\n",
    "        \n",
    "        one = two = None\n",
    "        \n",
    "        for i, item in enumerate(nums):\n",
    "            if one:\n",
    "                if item <= one[1]:\n",
    "                    one = (i, item)\n",
    "                    continue\n",
    "                    \n",
    "                if two :\n",
    "                    if item <= two[1]:\n",
    "                        two = (i, item)\n",
    "                    else: \n",
    "                        return True\n",
    "                else: \n",
    "                    two = (i, item)\n",
    "                    \n",
    "            else:\n",
    "                one = (i, item)\n",
    "                \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        if len(nums)<3 or nums==sorted(nums)[::-1]:\n",
    "            return False\n",
    "        p1,p2=float('inf'),float('inf')\n",
    "        for num in nums:\n",
    "            if num<=p1:\n",
    "                p1=num\n",
    "            elif num<=p2:\n",
    "                p2=num\n",
    "            else:\n",
    "                return True\n",
    "        return False\n",
    "    \n",
    "            \n",
    "                \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        \n",
    "        \n",
    "        one = 2 ** 31\n",
    "        two = 2 ** 31\n",
    "        for num in nums:\n",
    "            if num <= one:\n",
    "                one = num\n",
    "            elif num <= two:\n",
    "                two = num\n",
    "            else:\n",
    "                return True\n",
    "        return False\n",
    "        # 中间量dp保存\n",
    "        # dp = [1] * len(nums)\n",
    "        # i = 0\n",
    "        # while i < len(nums):\n",
    "        #     for j in range(i):\n",
    "        #         if nums[i] > nums[j]:\n",
    "        #             dp[i] = max(dp[i], dp[j]+1)\n",
    "        #             if dp[i] == 3:\n",
    "        #                 return True\n",
    "        #     i += 1\n",
    "        # return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        ans = []\n",
    "        for n in nums:\n",
    "            if not ans:\n",
    "                ans.append(n)\n",
    "            elif len(ans) == 1:\n",
    "                if n < ans[0]:\n",
    "                    ans[0] = n\n",
    "                elif n > ans[0]:\n",
    "                    ans.append(n)\n",
    "            elif len(ans) == 2:\n",
    "                if n > ans[1]:\n",
    "                    return True\n",
    "                elif n < ans[1] and n > ans[0]:\n",
    "                    ans[1] = n\n",
    "                elif n < ans[0]:\n",
    "                    ans[0] = n\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        if len(nums) < 3:\n",
    "            return False\n",
    "        small, mid = float('inf'), float('inf') #初始为最大值\n",
    "        for i in range(len(nums)):\n",
    "            if nums[i] <= small:    #当前数字小于small，更新small\n",
    "                small = nums[i]\n",
    "            elif nums[i] <= mid:    #当前数字大于small，小于mid，更新mid\n",
    "                mid = nums[i]\n",
    "            elif nums[i] > mid:     #当前数字大于mid\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sys\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        x1=sys.maxsize\n",
    "        x2=sys.maxsize\n",
    "        for x in nums:\n",
    "            if x <= x1:\n",
    "                x1=x \n",
    "            elif x <= x2:\n",
    "                x2 = x \n",
    "            else:return True\n",
    "        return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        dp = [1]*n\n",
    "\n",
    "        for j in range(n):\n",
    "            for i in range(j):\n",
    "                if nums[j] > nums[i]:\n",
    "                    dp[j] = max(dp[j], dp[i]+1)\n",
    "        return max(dp) >= 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        nums = [float(\"inf\")]+nums\n",
    "        dp=[[0 for _ in range(len(nums))]for _ in range(3)]\n",
    "        dp[1][0]=float(\"inf\")\n",
    "        dp[2][0]=float(\"inf\")\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]<dp[1][i-1]:\n",
    "                dp[0][i]=1\n",
    "                dp[1][i]=nums[i]\n",
    "                dp[2][i]=dp[2][i-1]\n",
    "            elif dp[1][i-1]<nums[i] and nums[i]<dp[2][i-1]:\n",
    "                dp[0][i] = 2\n",
    "                dp[1][i] =dp[1][i-1]\n",
    "                dp[2][i] =nums[i]\n",
    "            elif nums[i]>dp[2][i-1]:\n",
    "                dp[0][i] = 3\n",
    "                return True\n",
    "            else:\n",
    "                dp[0][i] = 0\n",
    "                dp[1][i] =dp[1][i-1]\n",
    "                dp[2][i] =dp[2][i-1]\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        if len(nums) < 3:\n",
    "            return False\n",
    "        \n",
    "        before = [nums[0]]\n",
    "        behind = [nums[-1]]\n",
    "        for i in range(1,len(nums)):\n",
    "            if nums[i]>before[-1]:\n",
    "                before.append(before[-1])\n",
    "            else:\n",
    "                before.append(nums[i])\n",
    "        for i in range(len(nums)-2,-1,-1):\n",
    "            if nums[i]<behind[-1]:\n",
    "                behind.append(behind[-1])\n",
    "            else:\n",
    "                behind.append(nums[i])            \n",
    "        rs = list(zip(before,nums,behind[::-1]))\n",
    "        for a,b,c in rs:\n",
    "            if a<b<c:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        num1, num2 = nums[0], float('inf')\n",
    "\n",
    "        for num in nums:\n",
    "            if num > num2:\n",
    "                return True\n",
    "            if num < num2 and num > num1:\n",
    "                num2 = num\n",
    "            if num < num1:\n",
    "                num1 = num\n",
    "                \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        dp = [2**31, 2**31]\n",
    "        for n in nums:\n",
    "            if n > dp[-1]:\n",
    "                return True\n",
    "            elif n > dp[0]:\n",
    "                dp[1] = min(dp[1], n)\n",
    "            dp[0] = min(dp[0], n)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n < 3:\n",
    "            return False\n",
    "        first, second = nums[0], float('inf')\n",
    "        for i in range(1,n):\n",
    "            if nums[i] > second:\n",
    "                return True\n",
    "            elif nums[i] > first:\n",
    "                second = nums[i]\n",
    "            else:\n",
    "                first = nums[i]\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        if len(set(nums))<3:return False\n",
    "        a,b=nums[0],inf\n",
    "        for num in nums:\n",
    "            if num>b:return True\n",
    "            elif num>a:b=num\n",
    "            else:a=num\n",
    "        return False\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        l = len(nums)\n",
    "        ans = [0] * l\n",
    "        stack = [0]\n",
    "        if len(set(nums)) < 3:\n",
    "            return False\n",
    "\n",
    "        for i in range(1,l):\n",
    "            while len(stack) != 0 and nums[i] > nums[stack[-1]]:\n",
    "                t = stack.pop()\n",
    "                ans[t] += 1\n",
    "            stack.append(i)\n",
    "        mi = nums[0]\n",
    "        for i in range(1,l):\n",
    "            if nums[i] > mi:\n",
    "                ans[i] += 1\n",
    "                if ans[i] == 2:\n",
    "                    return True\n",
    "            else:\n",
    "                mi = min(nums[i],mi)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        if len(set(nums))<3:\n",
    "            return False\n",
    "        for i in range(len(nums) - 1, 0, -1):\n",
    "            if nums[i] == nums[i - 1]:\n",
    "                del nums[i]\n",
    "\n",
    "        if len(nums)<3:\n",
    "            return False\n",
    "        dp=[]\n",
    "        for i in range(len(nums)):\n",
    "            dp.append(1)\n",
    "            for j in range(i):\n",
    "                if nums[j]<nums[i]:\n",
    "                    dp[i]=max(dp[i],dp[j]+1)\n",
    "            if max(dp)>=3:\n",
    "                return True\n",
    "        return False\n",
    "     \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        maxlist = nums[:]\n",
    "        jlist = []\n",
    "        for i in range(len(nums)-2, -1, -1):\n",
    "            if maxlist[i]<maxlist[i+1]:\n",
    "                jlist.append(nums[i])\n",
    "                maxlist[i] = maxlist[i+1]\n",
    "\n",
    "        \n",
    "        for i in range(len(jlist)-1):\n",
    "            if jlist[i]>jlist[i+1]:\n",
    "                return True\n",
    "                \n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        temp=[]\n",
    "        for i in range(len(nums)):\n",
    "            if len(temp)==0:\n",
    "                temp.append([nums[i]])\n",
    "            else:\n",
    "                l,r=0,len(temp)-1\n",
    "                while l<=r:\n",
    "                    mid=l+(r-l)//2\n",
    "                    if temp[mid][-1]>=nums[i]:\n",
    "                        r=mid-1\n",
    "                    else:\n",
    "                        l=mid+1\n",
    "                \n",
    "                if l==len(temp):\n",
    "                    temp.append([nums[i]])\n",
    "                else:\n",
    "                    temp[l].append(nums[i])\n",
    "            \n",
    "            if len(temp)==3:\n",
    "                return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        left = []\n",
    "        right = []\n",
    "        num1 = nums[0]\n",
    "        num2 = nums[-1]\n",
    "        for i in nums:\n",
    "            num1 = min(num1,i)\n",
    "            left.append(num1)\n",
    "        for i in range(len(nums) - 1, -1, -1):\n",
    "            num2 = max(nums[i],num2)\n",
    "            right.append(num2)\n",
    "        right.reverse()\n",
    "        for i in range(len(nums)):\n",
    "            if left[i] < nums[i] and nums[i] < right[i]:\n",
    "                return True\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        n=len(nums)\n",
    "        if n<3:\n",
    "            return False\n",
    "        leftmin=[0]*n\n",
    "        rightmax=[0]*n\n",
    "        leftmin[0]=float(\"inf\")\n",
    "        for i in range(1,n):\n",
    "            leftmin[i]=min(leftmin[i-1],nums[i-1])\n",
    "        rightmax[-1]=float(\"-inf\")\n",
    "        for i in range(n-2,-1,-1):\n",
    "            rightmax[i]=max(rightmax[i+1],nums[i+1])\n",
    "        for i in range(1,n-1):\n",
    "            if leftmin[i]<nums[i]<rightmax[i]:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n < 3:\n",
    "            return False\n",
    "        minleft = [0] * n \n",
    "        minleft[0] = nums[0]\n",
    "        for i in range(1, n):\n",
    "            minleft[i] = min(minleft[i-1], nums[i])\n",
    "        maxright = [0] * n\n",
    "        maxright[n-1] = nums[n-1]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            maxright[i] = max(maxright[i+1], nums[i])\n",
    "        for i in range(1, n-1):\n",
    "            if minleft[i-1] < nums[i] < maxright[i+1]:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:        \n",
    "        n = len(nums)\n",
    "        f = [inf] * 3\n",
    "        for i in range(n):\n",
    "            t = nums[i]\n",
    "            if f[2] < t:\n",
    "                return True\n",
    "            elif f[1] < t < f[2]:\n",
    "                f[2] = t\n",
    "            elif f[1] > t:\n",
    "                f[1] = t\n",
    "        return False\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n < 3:\n",
    "            return False\n",
    "        first, second = nums[0], 2**31 - 1\n",
    "        for i in range(1, n):\n",
    "            num = nums[i]\n",
    "            if num > second:\n",
    "                return True\n",
    "            if num > first:\n",
    "                second = num\n",
    "            else:\n",
    "                first = num\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        a = b = None\n",
    "        for num in nums:\n",
    "            if a is None or num <= a:\n",
    "                a = num \n",
    "            elif b is None or num <= b:\n",
    "                b = num\n",
    "            else:\n",
    "                return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n < 3:\n",
    "            return False\n",
    "        first, second = nums[0], float('inf')\n",
    "        for i in range(1, n):\n",
    "            num = nums[i]\n",
    "            if num > second:\n",
    "                return True\n",
    "            if num > first:\n",
    "                second = num\n",
    "            else:\n",
    "                first = num\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        l_nums = len(nums)\n",
    "        left_min = [nums[0]] * l_nums \n",
    "        right_max = [nums[-1]] * l_nums\n",
    "\n",
    "        for i in range(1, l_nums):\n",
    "            left_min[i] = min(left_min[i-1], nums[i])\n",
    "        print(left_min)\n",
    "\n",
    "        for i in range(l_nums-2, -1, -1):\n",
    "            right_max[i] = max(right_max[i+1], nums[i])\n",
    "        print(right_max)\n",
    "\n",
    "        for i in range(1, l_nums-1):\n",
    "            if left_min[i-1] < nums[i] < right_max[i+1]:\n",
    "                return True\n",
    "        \n",
    "        return False\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n <= 2: return False\n",
    "        if n == 3: return nums[0] < nums[1] < nums[2]\n",
    "\n",
    "        left, right = [nums[0]], collections.deque(nums[2: ])\n",
    "        left_counter, right_counter = collections.Counter(left), collections.Counter(right)\n",
    "        min_left, max_right = min(left), max(right)\n",
    "        left_counter\n",
    "        for i in range(1, n - 1):\n",
    "\n",
    "            if min_left < nums[i] < max_right:\n",
    "                return True\n",
    "            #deal with left\n",
    "            min_left = min(min_left, nums[i])\n",
    "            left_counter[nums[i]] += 1\n",
    "            left.append(nums[i])\n",
    "\n",
    "            #deal with right\n",
    "            poped = right.popleft()\n",
    "            if not right: return False\n",
    "            right_counter[poped] -= 1\n",
    "            if right_counter[poped] == 0: del right_counter[poped]\n",
    "            if max_right == poped and poped not in right_counter:\n",
    "                max_right = max(right)\n",
    "        return False\n",
    "\n",
    "            \n",
    "\n",
    "            \n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self,nums):\n",
    "        if len(nums)<3:\n",
    "            return False\n",
    "        else:\n",
    "            L,R=[nums[0]]+[0 for i in range(len(nums)-3)],[0 for i in range(len(nums)-3)]+[nums[len(nums)-1]]\n",
    "            for i in range(2,len(nums)-1):\n",
    "                L[i-1]=min(L[i-2],nums[i-1])\n",
    "            for i in range(len(nums)-3,0,-1):\n",
    "                R[i-1]=max(R[i],nums[i+1])\n",
    "            print(L)\n",
    "            print(R)\n",
    "            for i in range(1,len(nums)-1):\n",
    "                if L[i-1]<nums[i]<R[i-1]:\n",
    "                    return True\n",
    "            else:\n",
    "                return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "\n",
    "        left = []\n",
    "        right = []\n",
    "\n",
    "        min_val = math.inf\n",
    "        for i in range(n):\n",
    "            if nums[i] < min_val:\n",
    "                min_val = nums[i] \n",
    "            left.append(min_val)\n",
    "        \n",
    "        max_val = - math.inf\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            if nums[i] > max_val:\n",
    "                max_val = nums[i]\n",
    "            right.append(max_val)\n",
    "\n",
    "        right = right[::-1]\n",
    "\n",
    "        for i in range(1, n -1):\n",
    "            if left[i - 1] < nums[i] < right[i + 1]:\n",
    "                return True \n",
    "        \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        left_min = nums[0]\n",
    "        right = SortedList(nums[2:])\n",
    "        for j in range(1,n-1):\n",
    "            if nums[j]<left_min:\n",
    "                left_min = nums[j]\n",
    "            elif nums[j]>left_min:\n",
    "                index = right.bisect_right(nums[j])\n",
    "                if index<len(right):\n",
    "                    return True\n",
    "            right.remove(nums[j+1])\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        N = len(nums)\n",
    "        if N < 3:\n",
    "            return False\n",
    "        \n",
    "        min_stack = [nums[0]] * N\n",
    "        max_stack = [nums[-1]] * N\n",
    "\n",
    "        for i in range(1, N):\n",
    "            min_stack[i] = min(nums[i], min_stack[i - 1])\n",
    "        print(min_stack)\n",
    "\n",
    "        for i in range(N - 2, -1, -1):\n",
    "            max_stack[i] = max(nums[i], max_stack[i + 1])\n",
    "        print(max_stack)\n",
    "\n",
    "        for i in range(1, N - 1):\n",
    "            if min_stack[i] < nums[i] < max_stack[i]:\n",
    "                return True\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        # 0 1 2 4 5 6\n",
    "\n",
    "        # 枚举中间的数字\n",
    "        n = len(nums)\n",
    "        right = [-inf] * n\n",
    "        right[-1] = nums[-1] \n",
    "\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            right[i] = max(right[i + 1], nums[i])\n",
    "        \n",
    "        left = [inf] * n \n",
    "        left[0] = nums[0]\n",
    "\n",
    "        for i in range(1, n):\n",
    "            left[i] = min(left[i - 1], nums[i])\n",
    "        \n",
    "        print(left, right)\n",
    "        \n",
    "        for i in range(1, n - 1):\n",
    "            L = left[i - 1]\n",
    "            R = right[i + 1]\n",
    "            if L < nums[i] < R:\n",
    "                return True \n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        left_min = nums[0]\n",
    "        right_max = float('-inf')\n",
    "        rights = {}\n",
    "        for v in nums[2:]:\n",
    "            if v > right_max:\n",
    "                right_max = v\n",
    "            rights[v] = rights.get(v, 0) + 1\n",
    "        for i in range(1, len(nums)-1):\n",
    "            v = nums[i]\n",
    "            if v > left_min and v < right_max:\n",
    "                return True\n",
    "            if i ==len(nums) - 2:\n",
    "                return False\n",
    "            left_min = left_min if v > left_min else v\n",
    "            next_v = nums[i+1]\n",
    "            rights[next_v]-=1\n",
    "            if rights[next_v] == 0 and next_v == right_max:\n",
    "                right_max = max(nums[i+2:])\n",
    "        return False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        f = [inf] * 2\n",
    "        for i in range(n):\n",
    "            print(f)\n",
    "            t = nums[i]\n",
    "            if f[1] < t:\n",
    "                return True\n",
    "            elif f[0] < t < f[1]:\n",
    "                f[1] = t\n",
    "            elif f[0] > t:\n",
    "                f[0] = t\n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        left = [nums[0]]\n",
    "        for i in range(1,n):\n",
    "            left.append(min(nums[i],left[i-1]))\n",
    "        right = [-inf] * n\n",
    "        right[n-1] = nums[n-1]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            right[i] = max(nums[i], right[i+1])\n",
    "\n",
    "        for i in range(1,n-1):\n",
    "            if left[i] < nums[i] < right[i]:\n",
    "                return True\n",
    "\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # def compare(self, x, vx, y, vy):\n",
    "    #     if x < 0: return True\n",
    "    #     return vx < vy\n",
    "\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        # i = -2\n",
    "        # j = -1\n",
    "        # k = 0\n",
    "\n",
    "        # vi = 0\n",
    "        # vj = 0\n",
    "        # vk = nums[k]\n",
    "\n",
    "        # pos = k\n",
    "        # while pos + 1 < len(nums):\n",
    "        #     pos += 1\n",
    "        #     if self.compare(k, vk, pos, nums[pos]):\n",
    "        #         if j < k:\n",
    "        #             i = j\n",
    "        #             vi = vj\n",
    "        #         j = k\n",
    "        #         vj = vk\n",
    "        #         k = pos\n",
    "        #         vk = nums[pos]\n",
    "        #     elif self.compare(j, vj, pos, nums[pos]):\n",
    "        #         i = j\n",
    "        #         vi = vj\n",
    "        #         j = pos\n",
    "        #         vj = nums[pos]\n",
    "            \n",
    "        #     if (i >= 0 and j >= 0) and (i < j and j < k):\n",
    "        #         return True\n",
    "        \n",
    "        # return False\n",
    "\n",
    "        lmin_list = []\n",
    "        lmin = float(\"inf\")\n",
    "        rmax = float(\"-inf\")\n",
    "\n",
    "        for num in nums:\n",
    "            lmin_list.append(lmin)\n",
    "            lmin = min(lmin, num)\n",
    "        for index, num in zip(range(len(nums)-1, -1, -1), nums[::-1]):\n",
    "            if lmin_list[index] < num and num < rmax:\n",
    "                return True\n",
    "            rmax = max(rmax, num)\n",
    "        return False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "        n = len(nums)\n",
    "        if n < 3:\n",
    "            return False\n",
    "\n",
    "        leftMin = [nums[0]] * n\n",
    "        rightMax = [nums[n-1]] * n\n",
    "\n",
    "        for i in range(1, n):\n",
    "            leftMin[i] = min(nums[i], leftMin[i-1])\n",
    "\n",
    "        for i in range(n-2, -1, -1):\n",
    "            rightMax[i] = max(nums[i], rightMax[i+1])\n",
    "        \n",
    "        for i in range(1, n-1):\n",
    "            if leftMin[i - 1] < nums[i] < rightMax[i + 1]:\n",
    "                return True\n",
    "        \n",
    "        return False\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def increasingTriplet(self, nums: List[int]) -> bool:\n",
    "      l1=float(\"inf\")\n",
    "      l2=float(\"inf\")\n",
    "      for n in nums:\n",
    "        if n>l2:\n",
    "          return True\n",
    "        if n<l1:\n",
    "          l1=n\n",
    "        if n>l1:\n",
    "          l2=min(l2,n)\n",
    "      return False "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
